Digital data transmission over cables, fibers, radio, or acoustic links suffers from interference by various sources of noise. This decreases the signal-to-noise ratio (SNR) available at the receiver, which, in turn, can lead to errors in decoding the received data.
Coding schemes (error checking and correction (ECC)) are used to improve the probability that each bit of received data will be decoded correctly. However, the penalty for improved bit error rates (BER) is a reduction in the effective transmitted data rate due to the additional bits that must be transmitted with the data to correct the errors. For example, if eight bits need to be transmitted and four bits must be added to ensure that the eight bits are decoded correctly, the data rate is reduced by 50%.
In very poor SNR environments, the tradeoff between BER and the actual data rate is especially challenging. The underwater acoustic communications channel is typically a very poor SNR environment. One way of improving the actual data rate for a given SNR is to decrease the overhead required to maintain a given BER.
Direct sequence spread spectrum (DSSS) and turbo coding are both widely used in radio and acoustic communications. The function of DSSS is to spread data over a larger bandwidth, allowing the data to be recombined at the receiver and the noise power to be reduced (i.e. an improved SNR). Turbo coding (or any other forward error correction scheme) is then applied to the decoded DSSS signal in an attempt to minimize the BER.
One approach to turbo coding uses serially concatenated codes. Serially concatenated turbo codes were invented in the mid-1990's and are now taken to be the gold standard for forward error correction in very noisy environments. They are widely used in satellite communications and in cell phone communications. In this approach, each of the two decoders uses a slightly different algorithm to decode the noisy data stream, then the decoders exchange data and repeat the decoding process on the data block already processed by the other decoder. Over the course of numerous iterations of swapping and decoding, the best possible BER for the given SNR is achieved.
Currently, when DSSS and turbo coding are both used in a particular application, the two technologies are treated as two completely separate functions: the DSSS functional block processes the data in isolation, and then sends it to the turbo coding block, where iterative decoding is performed. Both technologies are described below in further detail.
DSSS
DSSS is well-known technology. Raymond L. Pickholtz, et al., Theory Of Spread-Spectrum Communications—A Tutorial, IEEE Trans Communications, Vol. COM-30, No. 5, p. 855-884 (May 1982); Harold P. E. Stern & Samy A. Mahmoud, Communication Systems Analysis and Design, Pearson Prentice Hall, NJ (2004). The purpose of DSSS is to spread the information contained in a signal over a wider bandwidth, then to de-spread it in a way that reduces the noise power relative to the signal power. This causes an effective increase in the SNR at the receiver, thereby decreasing the signal's susceptibility to interference from other signal sources or random noise. The spreading factor (N) is the increase in bandwidth resulting from the spreading operation; for example, a spreading factor of seven would increase the bandwidth by a factor of seven.
The standard method of spreading the signal is to create a pseudo-random binary code sequence (known as a pseudo random number or PRN) which is combined with the binary data to be transmitted. The PRN sequence is a multiple of the data block size. For example, if a spreading factor of seven were used, then the PRN would be seven times the size of the data block being transmitted. A number of algorithms can be used to create the PRN. The ‘best’ PRN is one that has the optimal combination of low autocorrelation and low cross-correlation with other codes of the same family. The autocorrelation property requires that if the PRN is correlated with any bit-shifted version of itself, the autocorrelation output will be significantly lower for any non-zero bit shift than for a bit shift of zero. This property allows the receiver to synchronize with the received PRN as reliably as possible. The cross-correlation property requires that the cross-correlation between any two codes in the PRN code family, for any bit shift, is much lower than the autocorrelation of each code with a bit shift of zero. This causes transmissions spread by other codes in the same PRN family to appear as random (uncorrelated) noise, maximizing the signal to noise ratio (SNR) of the decoded binary data. This allows simultaneous use of the same channel by several transmit/receive pairs using the same PRN family with minimal interference.
To create the output signal from the PRN sequence and the data block, each bit in the data block is exclusive-or'd (XOR'd) with bits in the PRN sequence. The number of bits used is defined by the spreading factor. If a spreading factor of seven is used, each data bit is XOR'd with seven PRN bits. The resulting data stream is pseudo-random, and has a bandwidth that is wider than the data stream. This transmission bandwidth is the data bandwidth multiplied by the spreading factor. The effect is that the original data stream is replaced with a pseudo-random data stream of higher bandwidth.
To decode the DSSS, the received binary data stream is synchronized with the original PRN sequence and the XOR operation repeated. By the nature of the XOR operation, the result (if no noise were present between the transmitter and receiver) would be the reproduction of the original data stream, but with each bit repeated N times (where N is the spreading factor). In a noisy environment, the received bit stream will not match the transmitted stream (i.e the spread data stream). After dispreading, rather than getting N bits of the same value (the value of the data bit), some of those N bits will have the wrong value, and a mechanism is required to decide the value of the original data bit. The usual mechanism is to take the average of the decoded bits (e.g. for a spreading factor of seven, the average value of the seven bits XOR'd from the received data stream is obtained), threshold the average (to get a result of 1 or 0), and use this as the best estimate of the original data bit.
It should be noted that the de-spreading mechanism is not considered to be part of the ECC used to protect the integrity of the data stream during DSSS transmission. Typically, a completely different ECC layer is applied to the data stream that emerges from the DSSS de-spreading process. In recent years, various forms of trellis and turbo coding have been used for this.
Turbo Coding
ECCs are used to detect and correct errors introduced when binary digital data is stored or transmitted. The simplest such code is the familiar parity bit used in serial data transmission and digital data storage. A single parity bit is capable of detecting that data corruption has occurred, but cannot correct it. To allow error detection and correction, more bits must be added to each byte of the data stream, creating an overhead that increases the bandwidth of that data stream. The higher the overhead, the larger the number of ECC bits there are per data byte and the better the data is protected. The ratio of overhead to data bits is extremely important, as many data operations are bandwidth-limited. Data transmission or reception by wired or wireless means are always bandwidth limited. The more bandwidth used by the ECC, the less there is available for data. Therefore, the efficiency of the ECC is very important—better data protection at a lower ECC overhead. Data integrity is usually measured as the BER, allowing performance comparison between different coding schemes.
The essence of turbo coding is to combine two relatively weak ECCs to provide much better ECC performance than previous ECC codes for a given overhead. The two codes are designed to be complementary, so that the overall coding scheme is much better at detecting and correcting errors than either code is on its own. The improvement in coding performance is highly non-linear. Christian B. Schlegel & Lance C. Perez, Trellis and Turbo Coding, IEEE Press, NJ, Ch. 12 (2004).
Two implementations of turbo codes are generally used: parallel concatenated and serially concatenated. The first implementations of turbo codes were parallel-concatenated codes, and the term turbo code is usually used to refer to parallel concatenation. However, the principles of the serial- and parallel-concatenated codes are very similar, and the term ‘turbo code’ is used herein to refer to both. Serially concatenated codes are more relevant to this discussion, and only serially concatenated codes will be described in detail.
Turbo Coding: Coding
A block diagram of Turbo coder 100, located on the transmitter side, is illustrated in FIG. 1. The data stream to be transmitted is divided into blocks (e.g. 4,096 bits). The block is processed by outer ECC coder 102, which transforms incoming uncoded words in the data block 101 to coded words in data block 103, also known as symbols, (which will be longer than the uncoded words of data block 101). The uncoded word of data block 101 can consist of any number of bits; the number of bits added during the coding operation will depend on the ECC code used. At the end of this outer coding operation, the data block will have expanded as additional ECC bits are added to the data bits.
After coding, the data is interleaved by interleaver 104. That is, each bit in the encoded data block maps to an arbitrary (randomized) location in interleaved data block 105. The effect of this process is to spread the data uniformly through interleaved data block 105, maximizing the distance between bits that formed part of the same ECC code word during the coding process. This minimizes the effect of multiple bit errors on the data integrity, as multiple random errors are much less likely to disrupt any single code word. Multiple errors are likely to cause multiple single bit errors in number of code words, rather than causing multiple errors in a single code word (which might so corrupt the word as to make the original data unrecoverable). The same random interleaving scheme is used for all incoming data blocks. The interleaver design is a critical part of the turbo coding scheme design.
Interleaved encoded data block 105 is now processed by inner ECC coder 106. This process adds some coding overhead bits to interleaved encoded data block 105, further expanding the encoded data block.
At this point, interleaved encoded data block 107 is transmitted through channel 108.
Note that the turbo coding process is completely deterministic and computationally undemanding.
Turbo Coding: Decoding
A block diagram of Turbo decoder 200, located on the receiver side, is shown in FIG. 2. Decoding serially concatenated turbo codes starts by passing received data block 201 through inner decoder 202. Received data block 201 comprises the same number of bits as interleaved encoded data block 107 that emerged from inner coder 106 during turbo coding. Generally, some noise will have corrupted the data stream.
Inner decoder 202 does not produce a ‘best estimate’ binary data stream; instead, it produces a likelihood ratio (LHR) for each bit it decodes. LHRs are commonly used in processes that must represent probabilities that are to be combined in some fashion. The LHR represents the probability that the bit is a ‘1’ to the probability that the bit is a ‘0’. If a data bit is definitely a ‘1’, then the LHR will be positive infinity. If the data bit is definitely a ‘0’, then the LHR will be negative infinity. An LHR of ‘1’ indicates that the data bit value is equally likely to be ‘1’ or ‘0’.
The LHR is determined by the decoding process. If no errors have occurred, the decoding process will produce a very high negative or positive LHR (indicating that the value of the decoded bit is known with high confidence). If multiple errors have occurred, then very the LHR values will be close to ‘1’. These LHRs will be the same for all bits of a decoded word, as the Inner Decoder on its own cannot determine which of the bits in the word are more or less reliable.
LHR block 203 emerging from inner decoder 202 is then de-interleaved (by interleaver 204) using the reverse of the randomized interleave mapping used during the coding process. The effect of this is to spread the LHRs through the data block, so that the LHRs are no longer next to the LHRs from the same word decoded in inner decoder 202.
At this point, de-interleaved LHR block 205 is of the same size, and in the same bit order, as encoded bit block 103 that emerged from outer coder 102 during the coding process. De-interleaved LHR block 205 is passed to outer decoder 206, which performs a probabilistic decode of data block 205 using the LHRs. The output from outer decoder 206 is a block of LHRs 207, indicating the confidence with which each bit value in the decoded word can be assigned. Again, the LHRs for a given code word will all show the same confidence level for each bit in the word.
The power of turbo coding stems from the next step, which is to interleave (at interleaver 209) LHR block 207 produced by outer decoder 206, and to feed it back into inner decoder 202 as a priori probabilities. Inner decoder 202 uses a Bayesian mechanism to combine the prior probabilities produced by outer decoder 206 during the decoding process, and again produces an output, which is an interleaved sequence of LHRs. This interleaved LHR block is de-interleaved (by de-interleaver 204), and introduced into outer decoder 206, which uses a Bayesian mechanism to perform a probabilistic decoding of the data block.
This passing of the LHR blocks between inner decoder 202 and outer decoder 206 continues until the LHRs produced at outer decoder 206 tend towards positive or negative infinity (indicating high confidence in the decoded bit values), or until the LHRs stagnate (no improvement in LHRs at the Outer Decoder on successive iterations) (decided at decision block 208). At this point, the decoding process is complete, and the LHRs are converted (in conversion block 310) to binary bit values.
During the iteration process, the LHRs emerging from the inner decoder 202 and outer decoder 206 are modified to remove the prior knowledge (i.e. the LHR values that were fed into the decoder), so that only the new knowledge (in the form of modified LHR values) is fed to the decoder.
As shown in Trellis and Turbo Coding, it is evident that the inner code should use feedback. Schlegel & Perez, Ch. 11. That is, the code word output for a given data word will depend on the previous code word output. The outer code can be any ECC, although convolutional codes are most efficient.
The turbo decoding process is non-deterministic, i.e. the number of iterations to produce a decoded bit block will vary with the amount of noise introduced during transmission. The implementation of turbo codes in software is complex compared to earlier coding schemes.
Turbo codes may be seen as trading simplicity of computational implementation for better performance. In many applications, the requirement for extra computing power at the decoder is justified by the improved BER.
Modulation
Digital data can be transmitted either as raw signal levels (e.g. +5V corresponding to a ‘1’, 0V to a ‘0’), or used to modulate some other waveform. Modulation serves two main purposes: it moves the data from baseband to the desired frequency for transmission and it can be used to increase the integrity of the data stream. This makes the demodulated signal less susceptible to corruption by noise during the transmission, propagation, and reception processes.
A number of different types of modulation are used: e.g. phase shift keying (PSK); amplitude shift keying (ASK); quadrature amplitude modulation (QAM); frequency shift keying (FSK) and chirp shift keying (CSK). This discussion will focus on the use of PSK, but the coding technique can be used for any modulation scheme, or combination of modulation schemes.
At its simplest, PSK uses a single bit's value to alter the relative phase of the sinusoid to be transmitted. For example, transmitting a ‘1’ might correspond to a sine wave, and transmitting a ‘0’ might correspond to a cosine wave. This is known as binary phase shift keying (BPSK), and the phase shift between ‘1’ and ‘0’ is 180 degrees. Quadrature Phase Shift Keying (QPSK) uses two bits together to define the phase of the output waveform. For example, ‘00’ might correspond to a phase of 0 degrees, ‘01’ to 90 degrees, ‘10’ to 180 degrees, and ‘11’ to 270 degrees. Clearly, other forms of PSK can be defined which will just use different phase offsets. For instance, 8PSK uses three bits and defines eight phase offsets.
Differential PSK is used to allow non-coherent demodulation of PSK. In this form of PSK, the phase offset used in for the transmission of the previous bit sequence is used as an input by the differential modulator, i.e., feedback of the modulation output is used to define the modulation for a given code word. For example, in QPSK the first time the sequence ‘00’ is transmitted, it might correspond to a phase offset of 90 degrees, but a succeeding sequence of ‘00’ might be given a phase offset of 180 degrees. Logic at the receiver tracks the phase of the incoming signal and applies a differential demodulation scheme to arrive at the original bit sequence.
Differential forms of other modulation schemes are also used, and can be substituted in this discussion.
Differential Coded Modulation
Differential Coded Modulation is a known modulation method. Sheryl L. Howard, & Christian Schlegel, Differential Turbo Coded Modulation with APP Channel Estimation, IEEE Trans Communications, p. 1397-1406 (August 2006); Sheryl L. Howard, et al., Differential Turbo Coded Modulation over Unsynchronized Channels, Proc. of W.O.C. 2002, Banff, AB, Canada (July 2002). In this scheme, the inner coder is also used to define the modulation used by a data sequence, using a differential form of a modulation scheme (e.g. Differential PSK). Differential modulation uses feedback (as required for a serially concatenated turbo code), and, therefore, is eligible for use as an inner code in a serial concatenated scheme. The outer code suggested by Howard and Schlegel was a conventional parity check code. A block diagram of a decoder as described by Howard and Schlegel is shown in FIG. 3.